package com.zhang.sort.cmp;

import com.zhang.sort.Sort;

/**
 * @author 张吉鑫
 * @Description 插入排序
 * @date 2021/4/12 20:51
 */
public class InsertionSort2<E> extends Sort<E> {
    /**
     * 插入排序优化版，
     *  思路是将【交换】转为【挪动】
     * ① 先将待插入的元素备份
     * ② 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
     * ③ 将待插入元素放到最终合适的位置
     */
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            int end = i;
            E element = array[end];
            while (end > 0) {
                if (cmpElement(element, array[end - 1]) < 0){
                    array[end] = array[end - 1];
                    end--;
                }else {
                    break;
                }
            }
            array[end] = element;
        }
    }
}
